Unless otherwise indicated herein, the materials described in this section are not prior art to the claims in this application and are not admitted to the prior art by inclusion in this section.
Many modern software applications display three-dimensional representations of objects and scenes as part of a user interface. Three-dimensional (3D) graphics are used in a wide range of applications including video games, simulations, virtual reality applications, geospatial information applications, and applications for mapping and navigation. In many applications, 3D graphics are more useful than two-dimensional (2D) graphics at depicting real-world environments and locations because the natural interaction between humans and the real-world occurs in three dimensions.
3D graphics are typically generated as a plurality of polygons that form the shapes of objects and other structures in a 3D virtual environment. In modern 3D graphics, the final display often includes additional graphical details that go beyond a simple rendering of polygons to provide additional detail and realism. Particularly, modern 3D graphics often include numerous graphical effects including, but not limited to, lighting effects, texturing, and shadow effects that the processor applies to the polygons to display the 3D environment. For example, rendered polygons typically receive one or more textures that simulate the appearance of materials in the real world such as wood, stone, metal, cloth, and many other materials. The appearance of a scene is also heavily influenced by the virtual light sources that illuminate the scene and form the basis for shadow effects. Finally, since most computing devices only display graphics with a two-dimensional (2D) display, the 3D graphics are converted into a rasterized 2D array of pixels for display. The 2D display depicts portions of the 3D scene in a similar manner to how a camera takes a 2D photograph of a 3D scene in the real world.
One particular useful application for 3D graphics is in 3D navigation map applications, such as those available on smart phones, tablet computers, and in-car infotainment systems. 3D building mesh data is often provided as a dataset for such 3D navigation map applications. FIG. 1 illustrates an exemplary polygon mesh 10 used by a 3D navigation map application to render a 3D building 12. However, the datasets used in such 3D navigation map applications often do not include 2D footprints for the 3D buildings, or only provide an over-simplified 2D footprint for some 3D buildings. 2D footprints are quite useful in a 3D navigation map application for several features.
However, accurate determination of 2D footprint faces several challenges. First, the method generally needs to work at run-time on hardware having relatively weak processing capabilities and with an existing dataset (such as those which may be commercially available), so as to not introduce additional effort in compiling the dataset and to minimize the impact on existing dataset update processes. However, many footprint generation methods are either efficient and inaccurate or accurate and inefficient, such that there is a trade-off between accuracy and performance. Second, the method generally needs to work with input data that contains separated buildings. However, many existing methods can't process input data which contains separated buildings. Accordingly, it would be advantageous to provide a method of determining 2D footprints that is both accurate and efficient. Additionally, it would be further advantageous if the method can process input data which contains separated buildings.